package com.leetcode.algorithm.y19.m03;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * leetcode-cn.com
 * (done)1002. 查找常用字符
 * (done)937. 重新排列日志文件
 * 
 * @author: jie.deng
 * @time: 2019年3月11日 上午10:12:19
 */
public class MySolution0311 {
	
	/**
	 * 1002. 查找常用字符
	 * 
	 * 给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。
	 * 
	 * 你可以按任意顺序返回答案。
	 * 
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 输入：["bella","label","roller"]
	 * 输出：["e","l","l"]
	 * 示例 2：
	 * 
	 * 输入：["cool","lock","cook"]
	 * 输出：["c","o"]
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= A.length <= 100
	 * 1 <= A[i].length <= 100
	 * A[i][j] 是小写字母
	 * @param strArr
	 * @return
	 */
	public List<String> commonChars(String[] strArr) {
		List<String> list = new ArrayList<String>();
		// key为公共字符，value为出现的次数的最小值
		Map<Character, Integer> map = null;
		for (String str : strArr) {
			Map<Character, Integer> chMap = new HashMap<Character, Integer>();
			for (char c : str.toCharArray()) {
				chMap.put(c, chMap.containsKey(c) ? 1 + chMap.get(c) : 1);
			}
			if (map == null) {
				map = new HashMap<Character, Integer>(chMap);
				continue;
			}

			// 移除非公共字符
//			Set<Character> set = map.keySet();	// map.keySet()元素的删除会引起map中元素的删除
			Set<Character> set = new HashSet<Character>(map.keySet());
			set.removeAll(chMap.keySet()); // 求差集
			for (Character ch : set) {
				map.remove(ch); // 移除非公共字符
			}

			// 修正数量
			for (Character ch : map.keySet()) {
				map.put(ch, Math.min(map.get(ch), chMap.get(ch)));
			}
		}
		if (map != null) {
			for (Character ch : map.keySet()) {
				Integer cnt = map.get(ch);
				while (cnt > 0) {
					list.add(ch + "");
					cnt--;
				}
			}
		}
		return list;
	}
    
    /**
     * 937. 重新排列日志文件
     * 
	 * 你有一个日志数组 logs。每条日志都是以空格分隔的字串。
	 * 
	 * 对于每条日志，其第一个字为字母数字标识符。然后，要么：
	 * 
	 * 标识符后面的每个字将仅由小写字母组成，或；
	 * 标识符后面的每个字将仅由数字组成。
	 * 我们将这两种日志分别称为字母日志和数字日志。保证每个日志在其标识符后面至少有一个字。
	 * 
	 * 将日志重新排序，使得所有字母日志都排在数字日志之前。字母日志按字母顺序排序，忽略标识符，标识符仅用于表示关系。数字日志应该按原来的顺序排列。
	 * 
	 * 返回日志的最终顺序。
	 * 
	 *  
	 * 
	 * 示例 ：
	 * 
	 * 输入：["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
	 * 输出：["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]
	 *  
	 * 
	 * 提示：
	 * 
	 * 0 <= logs.length <= 100
	 * 3 <= logs[i].length <= 100
	 * logs[i] 保证有一个标识符，并且标识符后面有一个字。
     * @param logs
     * @return
     */
	public String[] reorderLogFiles(String[] logs) {
		if (logs == null || logs.length == 0) {
			return null;
		}
		int len = logs.length;
		for (int i = 1; i <= len - 1; i++) {
			String log = logs[i];
			char ch = log.charAt(log.length() - 1);
			if (ch >= '0' && ch <= '9') {
				// 数字日志
				continue;
			}
			// 字母日志
			String wordKey = log.substring(log.indexOf(" ") + 1);
			int j = i - 1;
			for (; j >= 0; j--) {
				String logJ = logs[j];
				char chJ = logJ.charAt(logJ.length() - 1);
				if (chJ >= '0' && chJ <= '9') {
					// 数字日志后移一位
					logs[j + 1] = logs[j];
					continue;
				} else {
					// 字母日志
					String wordKeyJ = logJ.substring(logJ.indexOf(" ") + 1);
					if (wordKey.compareTo(wordKeyJ) < 0) {
						// 字母日志后移一位
						logs[j + 1] = logs[j];
					} else {
						break;
					}
				}
			}
			logs[j + 1] = log;
		}
		return logs;
	}

}
